package code501_600.code40_50;

import java.time.Year;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * 给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。
 *
 * 两个相邻元素间的距离为 1
 *
 * 输入：mat = [[0,0,0],[0,1,0],[0,0,0]]
 * 输出：[[0,0,0],[0,1,0],[0,0,0]]
 *
 * 输入：mat = [[0,0,0],[0,1,0],[1,1,1]]
 * 输出：[[0,0,0],[0,1,0],[1,2,1]]
 */
public class _542updateMatrix {

    /**
     * 思考 二维数组的广度遍历.
     * 自己代码有边界错误，题解代码如下。
     * @param mat
     * @return
     */
    public int[][] updateMatrix0(int[][] mat) {
        int[] dx = {1,0,0,-1};
        int[] dy = {0,1,-1,0};
        Queue<int[]> queue = new LinkedList<>();
        int xLenght = mat.length;
        int yLength = mat[0].length;
        for (int i = 0; i < xLenght; i++) {
            for (int j = 0; j < yLength; j++) {
                int length = 0;
                if(mat[i][j]==0){
                    continue;
                }
                // 对每一个二维数组中的值执行层序遍历
                queue.offer(new int[]{i,j});
                while (!queue.isEmpty()){
                    int[] origin = queue.poll();
                    for (int k = 0; k < 4; k++) {
                        int newX = origin[0] + dx[k];
                        int newY = origin[1] + dy[k];
                        if(newX>=0&&newY>=0&&newX<xLenght&&newY<yLength){
                            if(mat[newX][newY]==0){
                                queue.clear();
                                break;
                            }else{
                                queue.offer(new int[]{newX,newY});
                            }
                        }
                    }
                    ++length;
                }
                mat[i][j] = length;
            }
        }
        return mat;
    }


    static int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    /**
     *
     * 但在实际的题目中，我们会有不止一个 00。我们会想，要是我们可以把这些 00 看成一个整体好了。
     * 有了这样的想法，我们可以添加一个「超级零」，它与矩阵中所有的 00 相连，这样的话，任意一个 11 到它最近的 00 的距离，
     * 会等于这个 11 到「超级零」的距离减去一。由于我们只有一个「超级零」，我们就以它为起点进行广度优先搜索。
     * 这个「超级零」只和矩阵中的 00 相连，所以在广度优先搜索的第一步中，「超级零」会被弹出队列，而所有的 00 会被加入队列，
     * 它们到「超级零」的距离为 11。这就等价于：一开始我们就将所有的 00 加入队列，它们的初始距离为 00。这样以来，
     * 在广度优先搜索的过程中，我们每遇到一个 11，就得到了它到「超级零」的距离减去一，也就是 这个 11 到最近的 00 的距离
     *
     * 执行用时：     * 15 ms     * , 在所有 Java 提交中击败了     * 39.20%     * 的用户
     * 内存消耗：     * 42.4 MB     * , 在所有 Java 提交中击败了     * 68.22%     * 的用户
     * @param matrix
     * @return
     */
    public int[][] updateMatrix(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int[][] dist = new int[m][n];
        boolean[][] seen = new boolean[m][n];
        Queue<int[]> queue = new LinkedList<int[]>();
        // 将所有的 0 添加进初始队列中
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j] == 0) {
                    queue.offer(new int[]{i, j});
                    seen[i][j] = true;
                }
            }
        }

        // 广度优先搜索
        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            int i = cell[0], j = cell[1];
            for (int d = 0; d < 4; ++d) {
                int ni = i + dirs[d][0];
                int nj = j + dirs[d][1];
                if (ni >= 0 && ni < m && nj >= 0 && nj < n && !seen[ni][nj]) {
                    dist[ni][nj] = dist[i][j] + 1;
                    queue.offer(new int[]{ni, nj});
                    seen[ni][nj] = true;
                }
            }
        }

        return dist;
    }

    /**
     * 动态规划思想；递归将大问题变为小问题
     * @param matrix
     * @return
     */
    public int[][] updateMatrix1(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        // 初始化动态规划的数组，所有的距离值都设置为一个很大的数
        int[][] dist = new int[m][n];
        for (int i = 0; i < m; ++i) {
            Arrays.fill(dist[i], Integer.MAX_VALUE / 2);
        }
        // 如果 (i, j) 的元素为 0，那么距离为 0
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j] == 0) {
                    dist[i][j] = 0;
                }
            }
        }
        // 只有 水平向左移动 和 竖直向上移动，注意动态规划的计算顺序
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i - 1 >= 0) {
                    dist[i][j] = Math.min(dist[i][j], dist[i - 1][j] + 1);
                }
                if (j - 1 >= 0) {
                    dist[i][j] = Math.min(dist[i][j], dist[i][j - 1] + 1);
                }
            }
        }
        // 只有 水平向左移动 和 竖直向下移动，注意动态规划的计算顺序
        for (int i = m - 1; i >= 0; --i) {
            for (int j = 0; j < n; ++j) {
                if (i + 1 < m) {
                    dist[i][j] = Math.min(dist[i][j], dist[i + 1][j] + 1);
                }
                if (j - 1 >= 0) {
                    dist[i][j] = Math.min(dist[i][j], dist[i][j - 1] + 1);
                }
            }
        }
        // 只有 水平向右移动 和 竖直向上移动，注意动态规划的计算顺序
        for (int i = 0; i < m; ++i) {
            for (int j = n - 1; j >= 0; --j) {
                if (i - 1 >= 0) {
                    dist[i][j] = Math.min(dist[i][j], dist[i - 1][j] + 1);
                }
                if (j + 1 < n) {
                    dist[i][j] = Math.min(dist[i][j], dist[i][j + 1] + 1);
                }
            }
        }
        // 只有 水平向右移动 和 竖直向下移动，注意动态规划的计算顺序
        for (int i = m - 1; i >= 0; --i) {
            for (int j = n - 1; j >= 0; --j) {
                if (i + 1 < m) {
                    dist[i][j] = Math.min(dist[i][j], dist[i + 1][j] + 1);
                }
                if (j + 1 < n) {
                    dist[i][j] = Math.min(dist[i][j], dist[i][j + 1] + 1);
                }
            }
        }
        return dist;
    }
}
